翻訳と辞書 Words near each other ・ Karnad ・ Karnad Sadashiva Rao ・ Karnadi Anemer Bangkong ・ Karnafuly City Garden ・ Karnah ・ Karnai language ・ Karnail Gill ・ Karnail Singh Paras ・ Karmapa ・ Karmapa controversy ・ Karmapa International Buddhist Institute ・ Karmapolis ・ Karmarama (advertising agency) ・ Karmard ・ Karmardo ・ Karmarkar's algorithm ・ Karmarts ・ Karmaskalinsky District ・ Karmaskaly ・ Karmaskaly, Karmaskalinsky District, Republic of Bashkortostan ・ Karmasthana (astrology) ・ Karmatron ・ Karmaveer Bhaurao Patil College ・ Karmaveer Puraskaar ・ Karmawibhangga Museum ・ Karmayodha ・ Karmayogi ・ Karmayogi (1978 film) ・ Karmayogi (2012 film) ・ Karmayogi Ven. Kripasaran Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Karmarkar's algorithm ： ウィキペディア英語版 Karmarkar's algorithm Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice. Where $n$ is the number of variables and $L$ is the number of bits of input to the algorithm, Karmarkar's algorithm requires $O(n^\; L)$ operations on $O(L)$ digit numbers, as compared to $O(n^6\; L)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus :$O(n^\; L^2\; \backslash cdot\; \backslash log\; L\; \backslash cdot\; \backslash log\; \backslash log\; L)$ using FFT-based multiplication (see Big O notation). Karmarkar's algorithm falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but it moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data. == The algorithm == Consider a Linear Programming problem in matrix form: Karmarkar's algorithm determines the next feasible direction toward optimality and scales back by a factor . It is rather complicated, but described in a number of sources.〔http://dl.acm.org/citation.cfm?id=808695〕〔http://link.springer.com/article/10.1007%2FBF02579150〕〔http://onlinelibrary.wiley.com/doi/10.1002/j.1538-7305.1989.tb00316.x/abstract〕 〔Karmarkar N.K., An Interior Point Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, pp. 297308 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf〕 〔Karmarkar, N.K.., Riemannian Geometry Underlying Interior Point Methods for Linear programming, AMS series on Contemporary Mathematics 114, pp. 5175 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf〕 〔Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).〕 A simplified version, called the affine-scaling method, analyzed by others, can be described succinctly as follows. Note that the affine-scaling algorithm, while applicable to small scale problems, is not a polynomial time algorithm. For large scale and complex problems the original approach needs to be followed. Karmarkar also has extended the methodology 〔Karmarkar, N.K.,Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)〕〔Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).〕〔26. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Karmarkar's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.